#ifndef __LIST_H__
#define __LIST_H__

#include <iostream>
#include <string>

using namespace std;

template <class t> class List
{
public:
	//default constructor/destructor
	List();
	~List();

	//basic list operations
	void Add(t *value, string key);
	void Remove(string key);
	t* Get(string key);
	bool Exists(string key);
	int Length();

	//operators
	t* operator[](string key);
	t* operator[](int index);

protected:

	//linked list node
	struct ListNode
	{
		string key;
		t* Item;
		ListNode *next;
	};

	//pointers for linked list
	ListNode *m_Head;
	ListNode *m_Tail;

	//counter variable - to store number of items
	int m_count;
};


//////////////////////////////////////////////////////////////////////
//	Implementation of template starts here
//////////////////////////////////////////////////////////////////////


template <class t> List<t>::List()
{
	//initialize the list as NULL
	this->m_Head = NULL;
	this->m_Tail = NULL;
	this->m_count = 0;
}

template <class t> List<t>::~List()
{
	//following deletes the linked list

	//use the tail as a "helper" pointer - start it at the top
	this->m_Tail = this->m_Head;

	while(this->m_Head != NULL)
	{
		//move the pointer forward
		this->m_Head = this->m_Head->next;

		//delete the "old" head
		delete this->m_Tail;

		//move the "helper" pointer forward
		this->m_Tail = this->m_Head;
	}
}

template <class t> void List<t>::Add(t *value, string key)
{
	List<t>::ListNode *temp = new List<t>::ListNode();

	temp->Item = value;
	temp->key = key;
	temp->next = NULL;
	
	if(this->m_Head == NULL)
	{	//if there's nothing in the list add the first item
		this->m_Head = temp;
		this->m_Tail = this->m_Head;
	}
	else
	{	//there's already something in the list - attach to bottom
		this->m_Tail->next = temp;
		//move tail forward
		this->m_Tail = this->m_Tail->next;
	}

	this->m_count++;
}

template <class t> void List<t>::Remove(string key)
{
	ListNode* temp = this->m_Head;		//start at the top
	ListNode* holder;					//variable used during delete

	//check to see if it's the head of the list
	if((temp != NULL) && (temp->key == key))
	{
		//move the head forward
		this->m_Head = this->m_Head->next;

		//delete the item
		delete temp;
	}
	else{
		//look through the lsit for the item
		while((temp->next != NULL) && (temp->next->key != key))
		{
			temp = temp->next;
		}

		//check to see if we've found it
		if(temp->next != NULL)
		{
			//we have so remove it

			//hold on to the one we want to delete
			holder = temp->next;

			//re-assign the next pointer
			temp->next = temp->next->next;

			//delete the item to remove
			delete holder;
		}
	}

	this->m_count--;
}

template <class t> t* List<t>::Get(string key)
{
	//start at the top
	ListNode* temp = this->m_Head;

	//look for the item
	while((temp != NULL) && (temp->key != key))
	{
		temp = temp->next;
	}

	//if we found the item
	if(temp != NULL)
		//found it -  return the value
		return temp->Item;
	else
		//didn't find it - return nothing
		return NULL;
}

template <class t> bool List<t>::Exists(string key)
{
	//start at the top
	ListNode* temp = this->m_Head;

	//look for the item
	while((temp != NULL) && (temp->key != key))
	{
		temp = temp->next;
	}

	//if we found the item
	if(temp->next != NULL)
		//found it 
		return true;
	else
		//didn't find it - return nothing
		return false;
}

template <class t> int List<t>::Length()
{
	//return number of items in list
	return this->m_count;
}

template <class t> t* List<t>::operator[](string key)
{
	//index operator by key
	return this->Get(key);
}

template <class t> t* List<t>::operator[](int index)
{
	//index operator by index number
	ListNode* temp = this->m_Head;

	try
	{
		//if the number is valid
		if(index < this->m_count)
		{
			//progress to the correct item
			for(int i = 0; i < index; i++)
				temp = temp->next;

			//return the correct item
			return temp->Item;
		}
		else
			//index not valid, return nothing
			return NULL;
	}
	catch(...)
	{
		//there was an error, return nothing
		return NULL;
	}
}
#endif